package pers.lls.hds.sort.shell;

import java.util.Arrays;

/**
 * 插入排序
 * ⒈ 从第一个元素开始，该元素可以认为已经被排序
 * ⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
 * ⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
 * ⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 * ⒌ 将新元素插入到下一位置中
 * ⒍ 重复步骤2~5
 *
 * @author lilichai
 */
public class InsertSort {

    public void insertionSort(long[] arr) {
        int j, i;
        for (i = 1; i < arr.length; i++) {
            long temp = arr[i];
            j = i;
            while (j > 0 && arr[j - 1] >= temp) {
                arr[j] = arr[j - 1];
                --j;
            }
            arr[j] = temp;
        }
    }

    public static void main(String[] args) {

        InsertSort sort = new InsertSort();
        long[] arr = {1,3,5,9,2,6};
        sort.insertionSort(arr);
        Arrays.stream(arr).forEach(d -> System.out.print(d + " "));

    }
}

